Much effort is now being devoted toward designing digital electronic circuits which have the built-in capability of being "self-testing," that is, the ability to test their internal operation without the need for specialized test equipment. Developing a built-in self-test capability for a complex digital circuit containing separate structural elements is difficult because each different functional element often operates in a different manner. To simplify this task, many circuit designers use a "divide and conquer" strategy which entails developing a separate self-test routine for testing each separate structural element of the circuit.
To achieve complete self-testing of a complex digital circuit containing a read-only memory (ROM) comprised of an m.times.n matrix array of storage locations, a self-testing technique for the ROM is thus required. Presently, self-testing of a ROM is frequently accomplished by a technique known as "signature analysis". Signature analysis of a ROM is accomplished by sequentially shifting the stored bit out of each of the n cells in each successive one of the m rows of the ROM into a separate one of the inputs of a multiple input shift register (MISR) whose output is fed back to its input. As each bit is shifted into the corresponding one of the MISR inputs, the MISR exclusively OR's the bit with the bit previously received from the preceding column in the preceding row.
The bits of a selected sub-set of the exclusively OR'd bits are themselves exclusively OR'd and then fed back into the MISR input to enable the MISR to effectively perform a polynomial division on the ROM contents. At the completion of the polynomial division, there remains in the MISR a string of n bits which represents the remainder from the polynomial division and used as an indicator of the operation of the ROM. From a comparison of the actual residue to a reference value (which corresponds to the value of the residue when no faults are present), a determination can be made as to whether the ROM is faulty.
The advantage of the signature analysis technique for self-testing of a ROM is that the residue which remains in the MISR (representing the "signature" of the ROM) is only n bits long. Thus, by using signature analysis, the m.times.n bits of data stored in the ROM are effectively condensed or compacted into an n bit string. Consequently, if all possible error patterns are assumed to be equally likely, the possibility of error escape is 2.sup.-n. Although the likelihood of error escape using the conventional signature analysis may seen small, even a small likelihood of error is undesirable for high quality fault coverage. The error escape which occurs during conventional signature analysis is attributable to error masking and error cancellation. Error cancellation can occur each time each of a successive row of bits of the ROM is shifted into the MISR and is exclusively OR'd with the bit in the preceding column in the preceding row of the ROM thus, compacting the m.times.n bit ROM contents into an m+n-1 string. The bits which are exclusively OR'd in this manner are thus diagonally adjacent, and if each is erroneous, the errors tend to cancel each other out during the polynomial division. Consequently, the residue remaining in the MISR may not reflect the presence of an even number of erroneous, diagonally adjacent bits. Error masking arises from the compaction of the m.times.n-1 string into the n bit residue in the MISR. The compaction of the m.times.n bits in the ROM into an n bit MISR residue is effectively an m-to-1 mapping process. Failure to map one or more erroneous bits may give rise to an undetected error.
Therefore, there is a need for a self-test technique for a ROM which affords reduced incidence of error masking and error cancellation.